/**

This file is part of MaCI/GIMnet.

MaCI/GIMnet is free software: you can redistribute it and/or modify it 
under the terms of the GNU Lesser General Public License as published 
by the Free Software Foundation, either version 3 of the License, or 
(at your option) any later version.

MaCI/GIMnet is distributed in the hope that it will be useful, but WITHOUT 
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
License for more details.

You should have received a copy of the GNU Lesser General Public 
License along with GIMnet. (See COPYING.LESSER) If not, see 
<http://www.gnu.org/licenses/>.

**/
/**
 * \file
 * \brief Search structure for locating entries by ID - header.
 * \author Antti Maula <antti.maula@tkk.fi>
 *
 * This module implements a kind of map structure intended for storing
 * entries keyed by single integer. The stored data is just single
 * pointer, typed (void*) for maximum portability in different layers
 * of GIMnetAP. This module is capable of handling thousands of entries
 * with minimum overhead.
 *
 * The container is implemented as a hash table, combined to sorted
 * linked list. Querys are made by linear search on the linked list
 * found by hashvalue, and using knowledge about sorted list, search
 * is terminated as soon as value cannot exist anymore (greater value
 * reached)
 *
 * If even more optimization is required, the linear search could be
 * changed to use binary search or like. At the moment with the
 * following performance specs, this is by no means necessary.
 *
 * Performance characteristics benchmark using 1000 bins (reserving
 * total of 8000 Bytes of memory for hashtables), and 100000 elements.
 *
 * Adding 100000 entries...
 * ... Completed, in 168 milliseconds. (1.68us / entry)
 * Query 100000 entries...
 * ... Completed, in 155 milliseconds. (1.55us / entry)
 * Delete 100000 entries in reverse order
 * ... Completed, in 184 milliseconds. (1.84us / entry)
 *
 ******************************************************************************
 */
#ifndef _TCPHUB_IDMAP_H_
#define _TCPHUB_IDMAP_H_

/** Single entry stored in a ID map.
 */
typedef struct _idmap_entry
{
  unsigned int nodeID;       ///< ID of node.
  void *entry;               ///< Stored data.
  struct _idmap_entry *prev; ///< Pointer to prev
  struct _idmap_entry *next; ///< Pointer to next
} TIDMapEntry;

/** Bin container. Contains single entryarray.
 */
typedef struct _idmap_entry_bin
{
  TIDMapEntry *first;           ///< Array of entries begins here
  unsigned long int entryCount; ///< Number of entries in array.
} TIDMapEntryBin;


/** IDMap container entry.
 */
typedef struct _idmap
{
  unsigned int hashBinCount;      ///< Number of HashBins on this container.
  TIDMapEntryBin *idMapEntryBins; ///< Array of entryBins
  
  unsigned long int total_elements;
} TIDMap;


/** Structure used when enumerating all entries.
 */
typedef struct _idmap_iterator
{
  unsigned int bin; ///< Current bin.
  TIDMapEntry *entry; ///< Current entry.
} TIDMapEntryIterator;


/** Create new idMap.
 *
 * This function returns an allocated memory region typecasted to
 * TIDMap pointer. No initialization is performed, see idMapInit().
 *
 * @return Pointer to newly allocated but uninitialized structure.
 */
TIDMap *idMapCreate();


/** Initialize an IdMap, using specified hash bin count.
 *
 * This function initializes the IDmap, using \p aHashBinCount number
 * of bins. Number of bins is reversely comparable to the number of
 * collisions in the bins. The more bins, the more memory is required,
 * but the number of elements in the underlying linked list is
 * smaller, leading to faster inserts and lookups. Use a sane number
 * for your data. One bin takes 8 bytes of memory on 32 bit machine,
 * and 12 bytes on a 64 bit machines.
 * 
 * @param[in] im Pointer to TIdMap structure
 * @param[in] aHashBinCount Number of hashbins to initialize
 * @return Zero on success, non-zero on any error.
 *
 */
int idMapInit( TIDMap *im, 
               const unsigned int aHashBinCount);



/** Deinitalize IDMap.
 *
 * @param[in] im Pointer to TIdMap structure
 */
void idMapDeinit( TIDMap *im );


/** Destroy IDMap.
 *
 * \note The IDMap must be allocated with the idMapCreate() to use
 * this function.
 * 
 * @param[in] im Pointer to TIdMap structure
 */
void idMapDestroy( TIDMap *im );


/** Clear the whole idmap.
 *
 * This function clears the map, destroying all assigned elements.
 * \note This function does not touch the user provided data pointers.
 *
 * @param[in] im Pointer to TIdMap structure
 */
void idMapClear(TIDMap *im);


/** Add a new entry to idmap.
 *
 * @param[in] im Pointer to TIdMap structure
 * @param[in] aNodeID Node id (Key) to use
 * @param[in] aEntry Pointer to user defined data to bind to the given key.
 * @return Zero value on success (element succesfully added), 
 *         non-zero on any error, for example, when entry already existed.
 *
 */
int idMapAddEntry(TIDMap *im, const unsigned int aNodeID, void *aEntry);


/** Delete entry from idmap.
 *
 * @param[in] im Pointer to TIdMap structure
 * @param[in] aNodeID NodeID (key) to look for. If found, entry is destroyed.
 * @return Zero on success (element found and destroyed),
 *         non-zero on any error, for example, when no entry was found.
 */
int idMapDeleteEntry(TIDMap *im, const unsigned int aNodeID);


/** Return entry by key.
 *
 * This function returns a const pointer to element keyed with given
 * nodeid.
 * 
 * @param[in] im Pointer to TIdMap structure
 * @param[in] aNodeID NodeID (key) to look for. If found, a const pointer to 
 *            container element is returned.
 * @return    If requested entry is found, a const pointer to it is returned. Otherwise
 *            NULL.
 */
const TIDMapEntry *idMapGetEntry(const TIDMap *im, const unsigned int aNodeID);


/** Initialize a structure used for iterating through idmap elements.
 *
 * This function begins the iteration of the container by initializing
 * a structure which contains all the information required to execute
 * iteration.
 *
 * @param[in] im Pointer to TIdMap structure
 * @param[out] aIter Pointer to iterator structure to initialize
 */
void idMapGetNextEntryIterator(const TIDMap *im, TIDMapEntryIterator *aIter);


/** Get the next element in the idmap, as tracked by the iterator
 *
 * This function returns the next TIDMapEntry in the map. First call
 * to this function after calling the idMapGetNextEntryIterator()
 * function will return the very first element in the map.
 *
 * \note When this function is used, the underlying datastructure must
 * not be changed. In multi-thread applications, please make sure to
 * use proper locking.
 *
 * @param[in] im Pointer to TIdMap structure
 * @param[in] aIter Pointer to iterator structure used for tracking iteration status
 * @return Pointer to next element in the map, or NULL if no more elements available
 */
const TIDMapEntry *idMapGetNextEntry(const TIDMap *im, TIDMapEntryIterator *aIter);


/** Return the total number of elements stored in the idmap.
 *
 * @param[in] im Pointer to TIdMap structure
 * @return Total number of elements in the map. Naturally returns zero on empty map.
 */
inline unsigned long int idMapGetTotalElementCount(const TIDMap *im);


#endif //_TCPHUB_IDMAP_H_
